package com.clps.algorithm.chapter12.数组中第k大的数字;

import java.util.Random;

/**
 * 请输入一个乱序的数组中找出第k大的数字,例如数组[3,1,2,4,5,5,6]中第3大的数字是5;
 */
public class demo01 {
    public static void main(String[] args) {

    }

    public  int findKThLarGest(int[] nums,int k){
        int target = nums.length-k;
        int start = 0;
        int end = nums.length-1;
        int index= partition(nums,start,end);
        while (index!=target){
            if(index>target){
                end = index-1;
            }else{
                start = index+1;
            }
            index = partition(nums,start,end);
        }

        return  nums[index];
    }

    private int partition(int[] nums, int start, int end) {
        int random = new Random().nextInt(end - start+1)+start;
        swap(nums,random,end);

        int small = start-1;
        for (int i = start; i <end ; i++) {
            if(nums[i]<nums[end]){
                small++;
                swap(nums,i,small);
            }
        }
        small++;
        swap(nums,small,end);
        return  small;
    }

    private void swap(int[] nums, int index1, int index2) {
        if(index1 !=index2){
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    }
}

